package com.huawei.od;

import java.util.*;

/**
 * 787.k站中转内最便宜的航班
 * BFS/DFS
 */
public class TestEight {

    public static void main(String[] args) {
        System.out.println(findCheapestPrice(3, new int[][]{{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, 0, 2, 1));
    }

    /**
     * 最便宜的航班
     * @param n 城市个数
     * @param flights 航班从某地到某地
     * @param src 出发城市
     * @param dst 目的城市
     * @param k 最多经过多少站中转的路线
     * @return
     */
    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Queue<int[]> queue = new LinkedList<>();
        // 边缘
        List<int[]>[] edge = new List[n];
        int[] price = new int[n];
        for (int i = 0; i < n; i++) {
            edge[i] = new ArrayList<>();
            price[i] = Integer.MAX_VALUE;
        }

        for (int[] flight : flights) {
            edge[flight[0]].add(new int[]{flight[1], flight[2]});
        }

        price[src] = 0;
        queue.add(new int[]{src, 0, price[src]});

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            if (poll[1] > k) {
                break;
            }
            for (int[] ints : edge[poll[0]]) {
                if (price[ints[0]] > poll[2] + ints[1]) {
                    price[ints[0]] = poll[2] + ints[1];
                    queue.add(new int[]{ints[0], poll[1] + 1, price[ints[0]]});
                }
            }
        }
        return price[dst] == Integer.MAX_VALUE ? -1 : price[dst];
    }
}
